Task #M111B

There are a total of \(N\) acrobats in the circus. Each acrobat has their order number written on their shirt.

The fans visiting the circus have randomly rearranged the acrobats by shuffling their order, and now the acrobats are lined up in this new sequence.
Now, in order to amaze the audience, the acrobats want to bring the queue back to the sorted order (by shirt number) by following this operation repeatedly:

• The acrobats share a single ball, which starts at the 1st position in the lineup (this fact is not important). Until every acrobat stands in the position matching the number on their shirt, they perform the following operation as a group repeatedly:
  • The acrobat currently holding the ball (with a lineup position in the range \([2, N-1]\)) chooses any acrobat within that range and throws the ball to them (if the thrower is in the range, they may throw the ball to themselves).
  • The acrobat who catches the ball sits down (holding the ball), and at that moment, the acrobats immediately to their left and right jump over them and swap positions. In other words, if the ball is caught at position \(position\), then the acrobats at positions \(position - 1\) and \(position + 1\) swap places with each other.

Your task is to determine, for the given sequence, whether the acrobats can eventually rest (i.e., achieve the sorted order) using the allowed operations.

The first line of the input file contains one integer, \(T (1 \le T \le 10^4)\), the number of test cases.
For each test, the first line contains an integer, \(N(1 \le N \le 2 \times 10^5)\), the number of acrobats.

The next line contains \(N\) integers, a permutation of \([1,..,N]\), i.e., the order of the acrobats by shirt number.

It is guaranteed that the sum of all \(N\) over all test cases does not exceed \(2 \times 10^5\)!

For each test, in a separate line, print YES if it is possible to rearrange the acrobats into the sorted order by shirt number using the specified operations, otherwise print NO.